package AStar{
	/* 
	*	A寻路最短时间迭代算法实现
	* @Author:Michael
	* @blog:http://hi.baidu.com/wwwanq/
	*/
	public class Astar {
		private var _openList:Array;		// 开启标记列表
		private var _mapArr:Array;			// 地图数据矩阵
		private const STRAIGHT:uint = 10;	// 横坚方向上移动的评分
		private const SLANT:uint = 14000;		// 斜向移动的评分
		private var _w:uint;				// 地图矩阵的宽
		private var _h:uint;				// 地图矩阵的长
		private var _startX:int;			// 起始点X坐标
		private var _startY:int;			// 起始点Y坐标
		private var _endX:int;				// 结束点X坐标
		private var _endY:int;				// 结束点Y坐标
		
		/*
		* 构造方法
		*/
		//public function Astart(mapArr:Array) {
		public function Astar():void {
		}
		/*
		* 设置地图数据
		*/
		public function set map (mapArr:Array):void {
			if (mapArr != null && mapArr.length != 0) {
				_mapArr = mapArr;
				_h = mapArr[0].length;
				_w = mapArr.length;
			}
		}
		/*
		* 开始搜索路径
		*/
		public function findWay(startX:int, startY:int, endX:int, endY:int):Array {
			if (_mapArr != null) {
				_startX=startX;
				_startY=startY;
				_endX=endX;
				_endY=endY;
				//_mapArr[startX][startY] = -2;
				//_mapArr[endX][endY] = -3;
				
				var wayArr:Array = [];		// 初始化路径数组
				_openList = [];				// 初始化开启标记列表
				
				var mark:Mark=new Mark(_startX,_startY,null,0,0);
				var iX:int = _startX;
				var iY:int = _startY;
				while (true) {
					// 把当前点周围八个方向的点标记加入到开启标记列表。
					//addOpenList(newMark(iX + 1, iY - 1, true , mark));
					//addOpenList(newMark(iX + 1, iY + 1, true , mark));
					//addOpenList(newMark(iX - 1, iY + 1, true , mark));
					//addOpenList(newMark(iX - 1, iY - 1, true , mark));
					addOpenList(newMark(iX    , iY - 1, false, mark));
					addOpenList(newMark(iX + 1, iY    , false, mark));
					addOpenList(newMark(iX    , iY + 1, false, mark));
					addOpenList(newMark(iX - 1, iY    , false, mark));
					// 如果开启标记列表为空，则表示目标无法到达。
					if (_openList.length == 0) {
						break;
					}
					// 从开启标记列表中拿取路径评分F最小的节点标记。
					_openList.sortOn("f",Array.NUMERIC);
					// 迭代
					mark = _openList.shift();
					iX = mark.posX;
					iY = mark.posY;
					// 如果节点值为-3，则已到达目标。
					//if (-3 == _mapArr[iX][iY]) {
					if (_endX == iX && _endY == iY) {
						while (mark != null) {
							wayArr[wayArr.length] = mark.point;
							mark=mark.pMark;
						}
						break;
					}
				}
				
				mark  == null;
				return wayArr.reverse();
			} else {
				return null;
			}
		}
		/*
		* 把指定的标记加到标记列表，分别加入到Array变量和Object变量，前者提供下一轮的拿取，后者用来保存记录以便判断
		*/
		private function addOpenList(mark:Mark):void { 
			if (mark != null) {
				_openList[_openList.length] = mark;
				_openList[mark.posX+"_"+mark.posY] = mark;
				
			}
		}
		/*
		* 创建标记
		*/
		private function newMark(posX:int, posY:int, isSlant:Boolean ,pareMark:Mark):Mark {
			// 搜索的点是否在地图内。
			if (posX < 0 || posY < 0 || posX >= _w || posY >= _h) {
				return null;
			}
			// 是否为障碍物。
			if (_mapArr[posX][posY] == 1) {
				return null;
			}
			// 是否已经在开启标记列表中。
			if (_openList[posX + "_" + posY] != null) {
				return null;
			}
			// 是否是斜着走，如果是接下来判断左右或上下是否为障碍。
			/*if (isSlant) {
				if (_mapArr[posX][pareMark.posY] == 1 || _mapArr[pareMark.posX][posY] == 1) {
					return null;
				}
			}*/
			// 获取当前位置到目标位置X和Y上的距离。
			var absX:int = (_endX - posX)>0 ? (_endX - posX) : (posX - _endX);
			var absY:int = (_endY - posY)>0 ? (_endY - posY) : (posY - _endY);
			return new Mark(posX, posY, pareMark, isSlant ? SLANT : STRAIGHT, (absX + absY) * STRAIGHT);
		}
	}
}